The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(1(2(2(x1)))) → 0(1(0(2(2(x1)))))
0(1(2(2(x1)))) → 0(1(2(3(2(x1)))))
0(1(2(2(x1)))) → 0(2(2(1(3(x1)))))
0(1(2(2(x1)))) → 1(0(3(2(2(x1)))))
0(1(2(2(x1)))) → 1(2(0(3(2(x1)))))
0(1(2(2(x1)))) → 1(3(0(2(2(x1)))))
0(1(2(2(x1)))) → 1(3(2(0(2(x1)))))
0(1(2(2(x1)))) → 0(1(0(4(2(2(x1))))))
0(1(2(2(x1)))) → 0(2(1(3(2(3(x1))))))
0(1(2(2(x1)))) → 1(2(1(0(4(2(x1))))))
0(1(2(2(x1)))) → 1(5(0(4(2(2(x1))))))
0(1(2(2(x1)))) → 2(0(3(1(3(2(x1))))))
0(1(2(2(x1)))) → 2(1(1(0(4(2(x1))))))
0(1(2(2(x1)))) → 2(1(3(0(2(0(x1))))))
0(1(2(2(x1)))) → 2(1(3(3(2(0(x1))))))
0(1(2(2(x1)))) → 2(1(5(3(0(2(x1))))))
0(1(2(2(x1)))) → 2(2(1(3(0(5(x1))))))
0(1(2(2(x1)))) → 2(4(1(3(2(0(x1))))))
0(1(4(5(x1)))) → 1(5(0(4(1(x1)))))
0(1(4(5(x1)))) → 5(0(4(1(5(x1)))))
0(1(4(5(x1)))) → 5(4(1(5(0(x1)))))
0(1(4(5(x1)))) → 1(1(5(0(4(1(x1))))))
0(1(4(5(x1)))) → 5(4(1(5(5(0(x1))))))
5(1(2(2(x1)))) → 1(0(2(2(5(x1)))))
5(1(2(2(x1)))) → 1(3(5(2(2(x1)))))
5(1(2(2(x1)))) → 1(5(2(3(2(x1)))))
5(1(2(2(x1)))) → 1(5(0(2(2(3(x1))))))
5(1(2(2(x1)))) → 2(1(0(3(2(5(x1))))))
5(1(2(2(x1)))) → 3(1(3(5(2(2(x1))))))
5(1(2(2(x1)))) → 4(1(3(2(2(5(x1))))))
5(1(2(2(x1)))) → 5(1(0(4(2(2(x1))))))
5(1(2(2(x1)))) → 5(1(2(0(4(2(x1))))))
0(1(1(4(5(x1))))) → 3(1(0(4(1(5(x1))))))
0(1(2(2(2(x1))))) → 1(0(2(2(5(2(x1))))))
0(1(2(2(5(x1))))) → 1(5(0(4(2(2(x1))))))
0(1(2(4(5(x1))))) → 2(5(1(0(4(5(x1))))))
0(1(4(5(2(x1))))) → 1(0(4(2(0(5(x1))))))
0(1(4(5(5(x1))))) → 5(0(4(0(1(5(x1))))))
0(1(5(4(5(x1))))) → 1(5(0(4(1(5(x1))))))
0(5(1(2(2(x1))))) → 0(1(3(2(5(2(x1))))))
3(3(1(2(2(x1))))) → 1(3(2(0(3(2(x1))))))
3(4(4(0(5(x1))))) → 3(5(4(5(0(4(x1))))))
5(0(1(2(2(x1))))) → 1(3(2(0(5(2(x1))))))
5(1(2(2(5(x1))))) → 1(5(2(3(2(5(x1))))))
5(2(1(2(2(x1))))) → 2(1(3(5(2(2(x1))))))
5(2(4(0(5(x1))))) → 0(4(2(5(5(5(x1))))))
5(2(4(0(5(x1))))) → 0(4(5(4(2(5(x1))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1.
The certificate found is represented by the following graph.

Start state: 6257
Accept states: [6258, 6259, 6260]
Transitions:
6257→6258[0_1|0]
6257→6259[5_1|0]
6257→6260[3_1|0]
6257→6257[1_1|0, 2_1|0, 4_1|0]
6257→6261[2_1|1]
6257→6265[2_1|1]
6257→6269[3_1|1]
6257→6273[2_1|1]
6257→6277[2_1|1]
6257→6281[2_1|1]
6257→6285[2_1|1]
6257→6289[2_1|1]
6257→6294[3_1|1]
6257→6299[2_1|1]
6257→6304[2_1|1]
6257→6309[2_1|1]
6257→6314[2_1|1]
6257→6319[0_1|1]
6257→6324[0_1|1]
6257→6329[2_1|1]
6257→6334[5_1|1]
6257→6339[0_1|1]
6257→6344[5_1|1]
6257→6348[2_1|1]
6257→6352[2_1|1]
6257→6356[3_1|1]
6257→6361[5_1|1]
6257→6366[2_1|1]
6257→6371[5_1|1]
6257→6376[2_1|1]
6257→6381[2_1|1]
6257→6386[2_1|1]
6257→6391[2_1|1]
6257→6396[2_1|1]
6261→6262[2_1|1]
6262→6263[0_1|1]
6263→6264[1_1|1]
6264→6258[0_1|1]
6264→6319[0_1|1]
6264→6324[0_1|1]
6264→6339[0_1|1]
6265→6266[3_1|1]
6266→6267[2_1|1]
6267→6268[1_1|1]
6268→6258[0_1|1]
6268→6319[0_1|1]
6268→6324[0_1|1]
6268→6339[0_1|1]
6269→6270[1_1|1]
6270→6271[2_1|1]
6271→6272[2_1|1]
6272→6258[0_1|1]
6272→6319[0_1|1]
6272→6324[0_1|1]
6272→6339[0_1|1]
6273→6274[2_1|1]
6274→6275[3_1|1]
6275→6276[0_1|1]
6276→6258[1_1|1]
6276→6319[1_1|1]
6276→6324[1_1|1]
6276→6339[1_1|1]
6277→6278[3_1|1]
6278→6279[0_1|1]
6279→6280[2_1|1]
6280→6258[1_1|1]
6280→6319[1_1|1]
6280→6324[1_1|1]
6280→6339[1_1|1]
6281→6282[2_1|1]
6282→6283[0_1|1]
6283→6284[3_1|1]
6284→6258[1_1|1]
6284→6319[1_1|1]
6284→6324[1_1|1]
6284→6339[1_1|1]
6285→6286[0_1|1]
6286→6287[2_1|1]
6287→6288[3_1|1]
6288→6258[1_1|1]
6288→6319[1_1|1]
6288→6324[1_1|1]
6288→6339[1_1|1]
6289→6290[2_1|1]
6290→6291[4_1|1]
6291→6292[0_1|1]
6292→6293[1_1|1]
6293→6258[0_1|1]
6293→6319[0_1|1]
6293→6324[0_1|1]
6293→6339[0_1|1]
6294→6295[2_1|1]
6295→6296[3_1|1]
6296→6297[1_1|1]
6297→6298[2_1|1]
6298→6258[0_1|1]
6298→6319[0_1|1]
6298→6324[0_1|1]
6298→6339[0_1|1]
6299→6300[4_1|1]
6300→6301[0_1|1]
6301→6302[1_1|1]
6302→6303[2_1|1]
6303→6258[1_1|1]
6303→6319[1_1|1]
6303→6324[1_1|1]
6303→6339[1_1|1]
6304→6305[2_1|1]
6305→6306[4_1|1]
6306→6307[0_1|1]
6307→6308[5_1|1]
6308→6258[1_1|1]
6308→6319[1_1|1]
6308→6324[1_1|1]
6308→6339[1_1|1]
6309→6310[3_1|1]
6310→6311[1_1|1]
6311→6312[3_1|1]
6312→6313[0_1|1]
6313→6258[2_1|1]
6313→6319[2_1|1]
6313→6324[2_1|1]
6313→6339[2_1|1]
6314→6315[4_1|1]
6315→6316[0_1|1]
6316→6317[1_1|1]
6317→6318[1_1|1]
6318→6258[2_1|1]
6318→6319[2_1|1]
6318→6324[2_1|1]
6318→6339[2_1|1]
6319→6320[2_1|1]
6320→6321[0_1|1]
6321→6322[3_1|1]
6322→6323[1_1|1]
6323→6258[2_1|1]
6323→6319[2_1|1]
6323→6324[2_1|1]
6323→6339[2_1|1]
6324→6325[2_1|1]
6325→6326[3_1|1]
6326→6327[3_1|1]
6327→6328[1_1|1]
6328→6258[2_1|1]
6328→6319[2_1|1]
6328→6324[2_1|1]
6328→6339[2_1|1]
6329→6330[0_1|1]
6330→6331[3_1|1]
6331→6332[5_1|1]
6332→6333[1_1|1]
6333→6258[2_1|1]
6333→6319[2_1|1]
6333→6324[2_1|1]
6333→6339[2_1|1]
6334→6335[0_1|1]
6335→6336[3_1|1]
6336→6337[1_1|1]
6337→6338[2_1|1]
6338→6258[2_1|1]
6338→6319[2_1|1]
6338→6324[2_1|1]
6338→6339[2_1|1]
6339→6340[2_1|1]
6340→6341[3_1|1]
6341→6342[1_1|1]
6342→6343[4_1|1]
6343→6258[2_1|1]
6343→6319[2_1|1]
6343→6324[2_1|1]
6343→6339[2_1|1]
6344→6345[2_1|1]
6345→6346[2_1|1]
6346→6347[0_1|1]
6347→6259[1_1|1]
6347→6334[1_1|1]
6347→6344[1_1|1]
6347→6361[1_1|1]
6347→6371[1_1|1]
6348→6349[2_1|1]
6349→6350[5_1|1]
6350→6351[3_1|1]
6351→6259[1_1|1]
6351→6334[1_1|1]
6351→6344[1_1|1]
6351→6361[1_1|1]
6351→6371[1_1|1]
6352→6353[3_1|1]
6353→6354[2_1|1]
6354→6355[5_1|1]
6355→6259[1_1|1]
6355→6334[1_1|1]
6355→6344[1_1|1]
6355→6361[1_1|1]
6355→6371[1_1|1]
6356→6357[2_1|1]
6357→6358[2_1|1]
6358→6359[0_1|1]
6359→6360[5_1|1]
6360→6259[1_1|1]
6360→6334[1_1|1]
6360→6344[1_1|1]
6360→6361[1_1|1]
6360→6371[1_1|1]
6361→6362[2_1|1]
6362→6363[3_1|1]
6363→6364[0_1|1]
6364→6365[1_1|1]
6365→6259[2_1|1]
6365→6334[2_1|1]
6365→6344[2_1|1]
6365→6361[2_1|1]
6365→6371[2_1|1]
6366→6367[2_1|1]
6367→6368[5_1|1]
6368→6369[3_1|1]
6369→6370[1_1|1]
6370→6259[3_1|1]
6370→6334[3_1|1]
6370→6344[3_1|1]
6370→6361[3_1|1]
6370→6371[3_1|1]
6371→6372[2_1|1]
6372→6373[2_1|1]
6373→6374[3_1|1]
6374→6375[1_1|1]
6375→6259[4_1|1]
6375→6334[4_1|1]
6375→6344[4_1|1]
6375→6361[4_1|1]
6375→6371[4_1|1]
6376→6377[2_1|1]
6377→6378[4_1|1]
6378→6379[0_1|1]
6379→6380[1_1|1]
6380→6259[5_1|1]
6380→6334[5_1|1]
6380→6344[5_1|1]
6380→6361[5_1|1]
6380→6371[5_1|1]
6381→6382[4_1|1]
6382→6383[0_1|1]
6383→6384[2_1|1]
6384→6385[1_1|1]
6385→6259[5_1|1]
6385→6334[5_1|1]
6385→6344[5_1|1]
6385→6361[5_1|1]
6385→6371[5_1|1]
6386→6387[2_1|1]
6387→6388[5_1|1]
6388→6389[3_1|1]
6389→6390[1_1|1]
6390→6259[2_1|1]
6390→6334[2_1|1]
6390→6344[2_1|1]
6390→6361[2_1|1]
6390→6371[2_1|1]
6390→6392[2_1|1]
6390→6397[2_1|1]
6391→6392[5_1|1]
6392→6393[2_1|1]
6393→6394[2_1|1]
6394→6395[0_1|1]
6395→6258[1_1|1]
6395→6319[1_1|1]
6395→6324[1_1|1]
6395→6339[1_1|1]
6396→6397[5_1|1]
6397→6398[2_1|1]
6398→6399[3_1|1]
6399→6400[1_1|1]
6400→6335[0_1|1]

(2) BOUNDS(O(1), O(n^1))